package de.haw.gka.a1;

import java.util.*;

import org.jgrapht.Graphs;
import org.jgrapht.graph.AbstractGraph;
import org.jgrapht.graph.DefaultWeightedEdge;
import org.jgrapht.graph.WeightedPseudograph;
import org.jgrapht.util.FibonacciHeap;
import org.jgrapht.util.FibonacciHeapNode;


//http://keithschwarz.com/interesting/code/?dir=prim


public class AlgoPrimFibo extends AbstractSearchAlgo{
	
	private AbstractGraph<Knoten, DefaultWeightedEdge> graph;
	private WeightedPseudograph<Knoten, DefaultWeightedEdge> miniGraph;

	public AlgoPrimFibo(AbstractGraph<Knoten, DefaultWeightedEdge> graph){
		this.graph=graph;
		algo();
	}
	
	private void algo(){
		miniGraph= new WeightedPseudograph<Knoten, DefaultWeightedEdge>(DefaultWeightedEdge.class);
		List<Knoten> allK= new ArrayList<Knoten>(graph.vertexSet());
		//Radom ersten Knoten wählen
		Random generator = new Random();
		int random = generator.nextInt(graph.vertexSet().size()-1);
		Knoten first = allK.get(random);
		miniGraph.addVertex(first);

		//heap
		FibonacciHeap<Knoten> prioQ = new FibonacciHeap<Knoten>();
		Map<Knoten, FibonacciHeap<Knoten>> checkHeap = new HashMap<Knoten, FibonacciHeap<Knoten>>();
				
		addNachbarKnoten(prioQ, checkHeap, first);


        Iterator<Knoten> iterKnoten = graph.vertexSet().iterator();
        while(iterKnoten.hasNext() && !prioQ.isEmpty()){
           	Knoten lowK = prioQ.removeMin().getData();
			Knoten minKZiel = kleinsterNachbar(lowK);

			miniGraph.addVertex(lowK);
			miniGraph.addVertex(minKZiel);

            DefaultWeightedEdge dwe = graph.getEdge(lowK,minKZiel);
                //  System.err.println("DWE: " + dwe);
			boolean tmp = miniGraph.addEdge(graph.getEdgeSource(dwe), graph.getEdgeTarget(dwe), dwe);
            if(!tmp)
                miniGraph.addEdge(graph.getEdgeTarget(dwe),graph.getEdgeSource(dwe), dwe);

            System.err.println("DWE: " + dwe + " isAdd: " + tmp);
			addNachbarKnoten(prioQ, checkHeap, lowK);

		}
	}

    private void out(String str){
        System.out.println(str);
    }
	
	private void addNachbarKnoten(FibonacciHeap<Knoten> prioQ, Map<Knoten, FibonacciHeap<Knoten>> checkHeap, Knoten lowK) {
		for (Knoten knoten : Graphs.neighborListOf(graph, lowK)) {
			DefaultWeightedEdge kante = graph.getEdge(lowK, knoten);
			if (!checkHeap.containsKey(knoten)) {
				prioQ.insert(new FibonacciHeapNode<Knoten>(knoten), graph.getEdgeWeight(kante));
				checkHeap.put(knoten, prioQ);
			} else if (checkHeap.get(knoten).min() != null && checkHeap.get(knoten).min().getKey() > graph.getEdgeWeight(kante)) {
				prioQ.decreaseKey(checkHeap.get(knoten).min(), graph.getEdgeWeight(kante));
			}

		}
		
	}
	private Knoten kleinsterNachbar(Knoten aknoten){
		Knoten kleinster = null;
		double zwischen = Double.POSITIVE_INFINITY;
		for (Knoten knoten : Graphs.neighborListOf(graph, aknoten)) {
			DefaultWeightedEdge kante = graph.getEdge(aknoten, knoten);
		    if(Math.min(graph.getEdgeWeight(kante), zwischen) != zwischen){
                zwischen = graph.getEdgeWeight(kante);
                kleinster = knoten;
            }
		}
		return kleinster;
	}
	

	public WeightedPseudograph<Knoten, DefaultWeightedEdge> getMiniGraph(){
		return miniGraph;
	}
	
	public int getGewicht(){
		int tmp= 0;
        for(DefaultWeightedEdge dwe: miniGraph.edgeSet()){
             tmp = tmp + (int)miniGraph.getEdgeWeight(dwe);

        }
        return tmp;
	}
	
	@Override
	public List getTheShortestWay() {
		List tmp = new ArrayList();
        tmp.addAll(miniGraph.edgeSet());
        return  tmp;
	}

}
